package arithmetic.LeetCode;

import groovy.json.JsonOutput;
import java.util.Scanner;

/**
 * @author jiangfeng 2019/7/27 20:40
 * 背包问题
 */
public class BagSolution {

    public static void main(String[] args) {
      /*  Scanner scanner= new Scanner(System.in);
        while(scanner.hasNext()){
            String s = scanner.nextLine();
            String[] ss = s.split(" ");
            int price = Integer.valueOf(ss[0]);
            int size = Integer.valueOf(ss[1]);

            int i=0;
            int[][] arr = new int[size][3];
            while (i<size){
                s = scanner.nextLine();
                ss = s.split(" ");
                arr[i][0]= Integer.valueOf(ss[0]);
                arr[i][1]= Integer.valueOf(ss[1]);
                arr[i][2]= Integer.valueOf(ss[2]);
                i++;
            }

        }*/


        int constraint=10;
        // 物品 {重量,价值}
        int[][] arr = new int[][]{{2,6},{2,3},{6,5},{5,4},{4,6}};
        // [1,2,3],[3,7,12],5
        //int[][] arr2 =  new int[][]{{1,3},{2,7},{3,12}};
        bag(arr,10);
    }

    /**
     * 背包问题
     * @param arr
     * @param constraint
     */
    public static int[][] bag(int[][] arr,int constraint){
        int[][] bagMatrix = new int[arr.length][constraint+1];

        // 初始化解的矩阵  容量为0的时候都是0;
        // bagMatrix[i][j] 表示空间剩余j的时候 装入物品i的最优解
        for (int i = 0; i < arr.length; i++) {
            bagMatrix[i] = new int[constraint+1];
            bagMatrix[i][0] = 0;
        }

        for (int j = 1; j <= constraint; j++) {
            for (int i = 0; i < arr.length; i++) {
                // 重量大于剩余空间j时,则不能放入物品i,
                if (arr[i][0] > j) {
                    // 背包物品总价值就是不放当前物品的价值
                    if (i == 0) {
                        bagMatrix[i][j] = 0;
                    }else {
                        bagMatrix[i][j]= bagMatrix[i-1][j];
                    }
                }else {
                    // 物品重量小于 当前背包总容量,可以放下改物品
                    if (i == 0) {
                        bagMatrix[i][j] = arr[i][1];
                    } else {
                        int itemInBag = bagMatrix[i - 1][j - arr[i][0]] + arr[i][1];
                        bagMatrix[i][j] = bagMatrix[i - 1][j] > itemInBag ? bagMatrix[i - 1][j] : itemInBag;
                    }
                }
            }

        }
        System.out.println(JsonOutput.toJson(bagMatrix));

        // 计算装入物品:
        for (int i = 0; i < bagMatrix.length; i++) {

        }
        return bagMatrix;
    }




}
